package com.hanxiaozhang.sort;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 〈一句话功能简述〉<br>
 * 〈堆排序算法题〉
 *
 * @author hanxinghua
 * @create 2021/9/14
 * @since 1.0.0
 */
public class HeapTopic {

    public static void main(String[] args) {

        int[] array = {2, 4, 56, 22, 33, 11, 4};
        topic1(array, 5);
        System.out.println(Arrays.toString(array));
    }


    /**
     * 已知一个几乎有序的数组。几乎有序是指，如果把数组排好顺序的话，
     * 每个元素移动的距离一定不超过k，并且k相对于数组长度来说是比较小的。
     *
     * @param array
     * @param k
     */
    public static void topic1(int[] array, int k) {
        if (k == 0) {
            return;
        }
        // 默认小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int index = 0;
        // 0...K-1
        for (; index <= Math.min(array.length - 1, k - 1); index++) {
            heap.add(array[index]);
        }
        int i = 0;
        for (; index < array.length; i++, index++) {
            heap.add(array[index]);
            array[i] = heap.poll();
        }
        while (!heap.isEmpty()) {
            array[i++] = heap.poll();
        }
    }
}
